package leetcode_181_200;

public class numIslands_200 {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        //int[][] isFind = new int[m][n];  //格子是否被搜索过
        //直接对grid数组进行更改，访问过的设为2，即完成了搜索记录的效果
        int count = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == '1') { // 找到了一个新的岛
                    find(grid, i, j, m, n);
                    count++;
                }
        return count;
    }


    /**
     * 递归搜索，从左上角开始
     * @param grid   网格
     * @param x ,y    当前坐标
     * @param m      总行数
     * @param n      总列数
     */
    public void find(char[][] grid, int x, int y, int m, int n) {
        if (x < 0 || y < 0 || x > m - 1 || y > n - 1 ||grid[x][y] != '1' )
            return;
        grid[x][y] = '2';   //代表已经搜索过
        //向右
        find(grid, x, y + 1, m, n);
        //向下
        find(grid, x + 1, y, m, n);
        //向左
        find(grid, x, y - 1, m, n);
        //向上
        find(grid, x - 1, y, m, n);
        }
        //老版本
//    public void find(char[][] grid, int[][] isFind, int x, int y, int m, int n) {
//        if (isFind[x][y] != 1 && grid[x][y]=='1') {   //未被搜素过且是陆地（1）
//            flag=1;
//            isFind[x][y] = 1;
//            //向右
//            if (y != n - 1)
//                find(grid, isFind, x, y + 1, m, n);
//            //向下
//            if (x != m - 1)
//                find(grid, isFind, x + 1, y, m, n);
//            //向左
//            if (y != 0)
//                find(grid, isFind, x, y - 1, m, n);
//            //向上
//            if (x != 0)
//                find(grid, isFind, x - 1, y, m, n);
//        }
//    }
}
